共享記憶體

在這篇文章當中，我們探討的平行計算模型是，所有的處理器都有共享記憶體。看到這個詞應該很多朋友第一時間腦中都會蹦出一個詞彙叫做 共享經濟，想必相當划算 Race Condition（中文翻譯好像叫做競態條件，這什麼趣味名詞...）。不過就讓我們暫時假設可以好好地不用擔心 Race Condition 吧 (￣▽￣＃)﹏﹏

順便講講

這次我們要討論的是一個叫做 CREW PRAM 的平行計算模型。按照字面上的意思解讀，就是可以讓不同執行緒同時讀取同一個位址的記憶體、但是不能同時寫入、然後所有執行緒共享記憶體這樣。

平行演算法分析

要怎麼衡量一個平行演算法的工作效率呢？由於各家平行計算的系統架構都不同。我們來考慮一個最抽象化的模型吧！

☯ 總工作量 Work (W)

顧名思義，總工作量的定義就是所有處理器花在這支程式上的時間總和（不包含待命時間）。如果把待命時間也考慮進去的話，它叫做總花費 Cost。

☯ 工作深度 Depth (D)

顧名思義，工作深度就是根據計算的相依性，找出相依性最長的那件工作。以圖論的角度而言，如果我們把所有運算步驟的相依性繪製成一個有向無環圖，那麼工作的深度就是這個圖上的最長路徑長度。在某些模型中，這個數值又被稱呼為 Span（跨度）。

有了這些概念後，Brent 得出了以下結論：對於一個深度是 D、總工作量是 W 且擁有 P 個處理器的平行演算法來說，執行時間不超過 。

什麼樣子的演算法適合（被改造成）平行化？

可以想見，如果一個演算法內部的演算流程不太具有相依性，那麼就有機會改造成平行演算法。讓我們來舉個例子吧～比方說我們想要計算 個東西的總和。如果單純地寫一個 for 迴圈：

for (int i = 0; i < n; i++)
    sum += a[i];

那麼程式執行時必須要先把 a[0] 加到 sum、再把 a[1] 加到 sum、以此類推。不管怎麼加 sum 都必須要被更動到 次。這樣會造成相當大的深度。（題外話：大家可以想想看為什麼我們看到上面這段 code 的時候，不能隨意更動它變成平行的演算法？）如果這些資料本身被加起來的過程沒有相依性，我們就不應該寫出這樣的程式碼，因為這樣的程式碼會不利於平行化。

但如果我們就只是單純地想要計算 個數字的總和，誰先加誰後加沒什麼關係，我們可以把輸入拆成很多部份，讓 個處理器分別加總 個數字，最後再依序把他們加到某個記憶體的位址上。這樣一來，工作深度便成了 ，當 的時候會達到最小深度 ，比原本的深度 來得好呢。

同樣的想法可以繼續延伸下去，我們可以把它想成一棵加法樹，每一個節點代表一個子集合的加總問題。如果我們每次都把一個集合拆成 個更小的子集合，分別加完以後再把他們加起來。工作深度就會是 （證明略，大家可以想想為什麼是 而非 ）因此，如果我們讓 ，那麼該演算法的工作深度就會是 ，很棒吧！

今天先討論到這邊，我們明天繼續改造更多演算法～

參考資料

1. https://www.cs.cmu.edu/~guyb/papers/BM04.pdf